{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基于图的个性化推荐召回算法\n",
    "\n",
    "## 背景\n",
    "\n",
    "- 用户的行为很容易表示为图\n",
    "\n",
    "- 图推荐在个性化推荐领域效果显著\n",
    "\n",
    "## 二分图\n",
    "\n",
    "二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。[百度百科-二分图](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095?fr=aladdin)\n",
    "\n",
    "而我们的用户集合和物品集合正好是两个互不相交的子集，且每条边都连接着用户和物品，即用户-物品可以使用二分图描述。\n",
    "\n",
    "### 用户物品二分图\n",
    "\n",
    "![用户物品二分图](./img/user-item-graph.png)\n",
    "\n",
    "如上图，将用户和物品分成两个集合，将用户和行为过的物品链接起来，即成为了一张二分图。\n",
    "\n",
    "**问题：对userA 来说，item c 和 item e 哪个更值得推荐？**\n",
    "\n",
    "可以从以下几个方面考虑：\n",
    "\n",
    "- 两个顶点之间的连通路径数\n",
    "\n",
    "- 两个顶点之间连通路径长度\n",
    "\n",
    "- 两个顶点之间连通路径经过顶点的出度\n",
    "\n",
    "而相关性高的一对顶点一般具有入下特征：\n",
    "\n",
    "- 两个顶点之间有很多路径相连\n",
    "\n",
    "- 连接两个顶点之间的路径长度都比较短\n",
    "\n",
    "- 连接两个顶点之间的路径不会经过出度比较大的顶点\n",
    "\n",
    "举例来说：\n",
    "\n",
    "A 和 c、e 之间没有连接边，但是用户 A 和 物品 c 之间有两条长度为 3 的路径连接（A a B c 和 A d D c）， 用户 A 和物品 c 之间有一条长度为 3 的路径连接（A b C e）。那么，顶点 A 与 c 之间的相关性要高于顶点 A 与 e，因而物品 c 在 用户 A 的推荐列表中在 e 的前面。顶点 A 和 c 之间有两条路径（A a B c） 和 （A d D c），顶点出度分别为（3 2 2 2）和（3 2 2 2），所以两条路径对顶点的相关度贡献是一致的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
